"""
Problem 28: https://projecteuler.net/problem=28

Starting with the number 1 and moving to the right in a clockwise direction a 5
by 5 spiral is formed as follows:

    21 22 23 24 25
    20  7  8  9 10
    19  6  1  2 11
    18  5  4  3 12
    17 16 15 14 13

It can be verified that the sum of the numbers on the diagonals is 101.

What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed
in the same way?
"""

# _*_ conding:UTF-8 _*_
'''
@author = Kuperain
@email = kuperain@aliyun.com
@IDE = VSCODE Python3.8.3
@creat_time = 2022/5/10
'''


def generator(n: int) -> list:
    '''
    >>> print(generator(1))
    [[1]]
    >>> print(generator(3))
    [[7, 8, 9], [6, 1, 2], [5, 4, 3]]
    '''
    if n == 1:
        return [[1]]
    if n % 2 == 0:
        raise ValueError('n must be odd!')

    if n <= 1:
        return False
    if n == 2:
        return True

    res = [[0]*n for _ in range(n)]
    res[n//2][n//2] = 1

    for c in range(1, (n+1) // 2):  # middle(1), as cycle 0
        size = 2*c+1
        rightupValue = size**2
        # (i,j) , index of rightup element at current cycle
        i, j = n//2 - c, n//2 + c
        offset = 0
        for up in range(j, j-size, -1):
            res[i][up] = rightupValue - offset
            offset += 1

        for left in range(i+1, i+size):
            res[left][j-size+1] = rightupValue - offset
            offset += 1

        for down in range(j-size+2, j+1):
            res[i+size-1][down] = rightupValue - offset
            offset += 1

        for right in range(i+size-2, i, -1):
            res[right][j] = rightupValue - offset
            offset += 1

    return res


def solution(n: int = 1001) -> int:
    '''
    sum of the numbers on the diagonals

    >>> assert solution(5) == 101
    '''
    g = generator(n)
    return sum([g[i][j] for i in range(n) for j in range(n) if i == j or i+j == n-1])


if __name__ == "__main__":
    import doctest
    doctest.testmod(verbose=False)

    print(solution())
    # 669171001
